1. Field of the Invention
The invention relates generally to methods and apparatus used for performing non-volatile memory "heap management", defined herein as allocating and/or freeing blocks of memory as requested by a user, in a manner that protects the integrity of the heap management data structure stored in the memory.
More particularly, the invention relates to methods and apparatus for performing heap management in programmable recording instruments used to record process data; and protecting the integrity of data structures stored in non-volatile memory included such instruments should a power failure or power shut down occur while heap management operations are in progress.
Furthermore, according to the invention, methods and apparatus are provided for (a) validating the integrity of the aforementioned data structures quickly on power up of the recording instrument; (b) finishing certain predetermined processes, that were in progress when a power failure occurred, at the time when the recording instrument is powered back up; (c) locating any memory allocated to a user prior to a power failure or shut down; and (d) assuring the user, whenever power is restored to the system, that only pointers to previously allocated data blocks containing valid data are provided in response to users requests for such pointers.
2. Description of the Related Art
Methods and apparatus are well known for managing the heap in, for example, volatile random access memory (VRAM). For example standard, commercially available C malloc (memory allocation) and free (memory deallocation) utilities, used for VRAM heap management purposes, are well known by those skilled in the art.
In particular, heap management for VRAM can be accomplished by the user maintaining two lists. One list is a list of all blocks of memory that are not in use, often referred to as a "free list" of memory blocks; and a second list, which is a list of all memory blocks that are in use, often referred to as the "used" or "allocated" list of memory blocks.
Techniques for VRAM list management per se, including procedures for adding and removing memory blocks from the aforementioned lists; procedures for efficiently locating properly sized blocks of memory to allocate; procedures for splitting and coalescing blocks for increasing allocation options and facilitating the efficient use of memory resources, etc., are also all known in the art.
In the VRAM context, when the recording instrument is powered down intentionally or due to a power failure, none of the memory is sustained unless an alternate source of power exists. Assuming no such alternate power source, all the heap is free (available to be allocated again) when the machine is powered back up. There is no need to worry about data structure corruption or having to locate previously allocated memory on power up.
In applications where it is important to insure the integrity of heap management data structures, and other data stored in memory, well known approaches for achieving this objective include the use of an uninterruptible power source to insure power at all times to the recording instrument itself; and/or the use of some type of "non-volatile" or "backed" memory device in the instrument, i.e., using a memory device that preserves the data structures and data stored therein for at least some predetermined time period.
Examples of non-volatile (backed) memory devices include capacitor backed random access memory (RAM), which preserves data stored therein over the time frame during which the capacitor discharges (thereby provides power to the memory device); battery backed RAM, etc.
For these types of recording instruments (those including some form of non-volatile memory for storing heap management data structures and process data); the prior art memory allocation and memory free utilities are problematic since: (a) if power goes down while removing or adding an entry to a list, parts of the list can be lost or the lists can be cross-linked depending on the list management technique used; (b) if power goes down while splitting or coalescing blocks, block sizes can be wrong; and (c) there is no way to get memory allocated before the power went down back to the user and at the same time assure the integrity of the previously allocated memory, after a power failure or reset has occurred.
Another prior art technique for preserving the integrity of data structures and the data stored in a non-volatile memory device, while avoiding the aforementioned problems associated with splitting and coalescing memory blocks, is to require the use of memory blocks having fixed pre-allocated sizes for storing data. This technique, although addressing some of the aforementioned problems, wastes often limited non-volatile memory resources.
Still other prior art methods and apparatus for recording process data are set forth in copending patent application Ser. No. (attorney Docket Number LT-2973), filed on Apr. 25, 1995, assigned to the same assignee as the present invention. This copending patent application is hereby incorporated by reference for background purposes.
In the incorporated copending application, backed RAM is preferably used to stage data transfer to a removable storage medium (like a floppy disk) inserted into the recording instrument. According to a preferred embodiment of the invention described in the incorporated copending patent application, the backed RAM contents are periodically transferred to the removable media; but in the mean time the backed RAM is used to store potentially large quantities of process data over extended periods of time.
In applications such as those described in the incorporated copending patent application, i.e., for recording instruments being used to record process data where the instrument itself is not typically furnished with an uninterruptible power source, where the recording instrument utilizes non-volatile memory for data integrity purpose with the quantity of such memory space being limited and at a premium, etc., it is desirable to efficiently allocate the non-volatile memory resource (e.g., the backed RAM) to maximize the number of data blocks that can be made available for storing the varying quantities of information collected in the process data gathering and recording context.
More generally, for all of the reasons set forth hereinabove, it would be desirable to provide methods and apparatus for performing heap management in programmable recording instruments used to record process data; and at the same time protect the integrity of data structures stored in non-volatile memory included in such instruments should a power failure or power shut down occur while heap management operations are in progress.
Furthermore, it would be desirable to provide methods and apparatus for validating the integrity of the aforementioned data structures quickly on power up of the recording instrument.
Still further, it would be desirable to provide methods and apparatus for insuring the stability of further heap management processing following the occurrence of a power failure of reset.
Further yet, it would be desirable to provide methods and apparatus for locating any memory allocated to a user prior to a power failure or shut down; and assuring, whenever power is restored to the instrument, that only pointers to previously allocated data blocks containing valid data are provided in response to users requests for such pointers.